#pragma once

#include <set>
#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *
 * */
static vector<vector<int>> result;
static vector<int> temp;

static void back(vector<int> &nums, int target, int &sums, int index) {

    //排序
    sort(nums.begin(), nums.end());

    if (sums == target && temp.size() == 4) {


        result.push_back(temp);
        return;
    }


    for (int i = index; i < nums.size(); ++i) {
        temp.push_back(nums[i]);
        sums = sums + nums[i];
        back(nums, target, sums, i + 1);
        sums = sums - temp[temp.size() - 1];
        temp.pop_back();


    }


}


//[1,0,-1,0,-2,2], target = 0
// -2 -1 0 0 1 2
//这个好像不能那个.....回溯 不重复还好说
vector<vector<int>> fourSum1(vector<int> &nums, int target) {

    int sums = 0;

    back(nums, target, sums, 0);


    set<vector<int>> s(result.begin(), result.end());
    result.assign(s.begin(), s.end());

    return result;
}


/*
 * 4个指针 怎么说去重哪里都不是我写的了 。。。。哎
 * */
vector<vector<int>> fourSum(vector<int> &nums, int target) {

    sort(nums.begin(), nums.end());
    vector<vector<int>> result1;
    for (int i = 0; i < nums.size(); ++i) {
        int temp1 = nums[i];

        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        for (int j = i + 1; j < nums.size(); ++j) {
            //这里再次去重为什么可以这样去重 ？就去重费劲 自己仔细想想
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }

            int temp2 = nums[j];//双指针了
            int low = j + 1;
            int high = nums.size() - 1;
            while (low < high) {


                if ((temp1 + temp2) == target - nums[low] - nums[high]) {
                    result1.push_back(vector<int>{temp1, temp2, nums[low], nums[high]});

                    // 去重逻辑应该放在找到一个四元组之后
                    while (high > low && nums[high] == nums[high - 1]) high--;

                    while (high > low && nums[low] == nums[low + 1]) low++;

                    // 找到答案时，双指针同时收缩
                    high--;
                    low++;

                } else if ((temp1 + temp2) < target - nums[low] - nums[high])
                    low++;
                else
                    high--;

            }


        }

    }

    return result1;
}


//卡 long long 用例纯属恶心人

vector<vector<int>> fourSum(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ret;
    for (int i = 0; i < nums.size(); ++i) {
        if (i > 0 && nums[i] == nums[i - 1])
            continue;


        for (int j = i + 1; j < nums.size(); ++j) {
            if (j > 0 && j > i + 1 && nums[j] == nums[j - 1])
                continue;

            int low = j + 1;
            int high = nums.size() - 1;
            while (low < high) {
                long long sum = (long long) ((long long) nums[i] + (long long) nums[j] + (long long) nums[low] +
                                             (long long) nums[high] - (long long) target);
                //(temp1+temp2)==target-nums[low]-nums[high]

                if (sum == 0) {
                    vector<int> t = {nums[i], nums[j], nums[low], nums[high]};
                    ret.push_back(t);
                    low++;
                    while (low < high && nums[low] == nums[low - 1])
                        low++;

                    high--;

                    while (low < high && high >= 0 && nums[high + 1] == nums[high])
                        high--;

                } else if (sum < 0) {
                    //说明low应该+了
                    ++low;
                } else {
                    --high;
                }

            }

        }

    }


    return ret;

}
